// fastlock.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <marusdefs.h>


#include <iostream>
#ifdef _UNICODE
    #define _tcout _STD wcout
#else
    #define _tcout _STD cout
#endif

#define _$ _tcout 
#define $_ _STD endl 

class prec_timer  
{
private:
	__int64 _start;
	__int64 _stop;

public:
	prec_timer() 
        : _start(0)
        , _stop(0)
    {
	}

    static  
	double to_double(const LARGE_INTEGER& val) throw()
    {
        return (double( val.u.HighPart) * -1. + val.u.LowPart);
	}

    static  inline
	double to_double(const __int64& val) throw()
    {
        return to_double(*(LARGE_INTEGER*)&val);
	}
    static
    double  getFreq() throw()
    {
	    LARGE_INTEGER freq;
        ::QueryPerformanceFrequency(&freq);
        return (to_double(freq));
    }

    static inline
    double  frequency() throw()
    {
        static double freq(getFreq());
        return freq;
    }

    static double duration(double start_, double stop_)
    {
		return (stop_ - start_)/frequency();
    }

    static  inline
    double  now()
    {
	    LARGE_INTEGER time;
        _ReadBarrier();
        ::QueryPerformanceCounter((LARGE_INTEGER*)&time);
        return to_double(time);
    }

	inline void start() 
    {
        _ReadBarrier();
        ::QueryPerformanceCounter((LARGE_INTEGER*)&_start);
        _stop = _start;
    }

	inline double stop() 
    {
        _ReadBarrier();
        ::QueryPerformanceCounter((LARGE_INTEGER*)&_stop);
        return duration(to_double(_start), to_double(_stop));
	}

    double elapsed()
    {
        return duration(to_double(_start), now());
    }

    double restart()
    {
        double ret(elapsed());
        start();
        return (ret);
    }
};

class   CSysInfo
{
private:
    static SYSTEM_INFO&   si()
    {
        static  SYSTEM_INFO ssi;
        static bool initialized = false;
        if (!initialized)
        {
            ::GetSystemInfo(&ssi);
            initialized = true;
        }
        return ssi;
    }

    CSysInfo();
    CSysInfo(const CSysInfo&);
    CSysInfo& operator=(const CSysInfo&);
public:

    static inline DWORD NumberOfProcessors()
    {
        return  si().dwNumberOfProcessors;
    }
    static inline LPVOID   MinAppAddress()
    {
        return si().lpMinimumApplicationAddress;
    }
    static inline LPVOID   MaxAppAddress()
    {
        return si().lpMaximumApplicationAddress;
    }
    static inline DWORD   PageSize()
    {
        return si().dwPageSize;
    }
    static inline DWORD    Granularity()
    {
        return si().dwAllocationGranularity;
    }
};

static inline DWORD NumProcessors()
{
    return CSysInfo::NumberOfProcessors();
}

#define RAISE_LASTERROR(x)    if (!(x)) { ULONG_PTR nErrCode = GetLastError(); RaiseException(0xDEADC0DE, EXCEPTION_NONCONTINUABLE_EXCEPTION, 1, &nErrCode); }

//static inline
//bool    active_spinning(int& counter_)
//{
//    if (_value >= 20)
//        return false;
//
//    if (_value < 10) 
//        YieldProcessor();
//    else if (_value < 20)
//        for (int i = 0; i != 50; ++i) 
//            YieldProcessor();
//    ++counter_;
//    return true;
//}
//
static inline
bool    passive_spinning(int& counter_)
{
    if (counter_ > 6)
        return false;

    if (counter_ < 2) // 2 time in the same processor
        ::SwitchToThread();
    else if (counter_ < 4) // 2 times
        ::Sleep(0);
    else if (counter_ < 6)
        ::Sleep(1);

    ++counter_;
    return true;
}

class   hybrid_spin
{
protected:
    int _value;
public:
    hybrid_spin()
        : _value(0) // backoff is initialized to 0
    {}

    inline void operator() () 
    {     
        // try active spinning first
        if (_value < 10) 
            YieldProcessor();
        else if (_value < 20)
            for (int i = 0; i != 50; ++i) 
                YieldProcessor();
        // still waiting... try passive spinning now
        else if (_value < 22) // 2 time in the same processor
            ::SwitchToThread();
        else if (_value < 24) // 2 times in the same processor
            ::Sleep(0);
        else if (_value < 26)
            ::Sleep(1);
        else {
            ::Sleep(10);
            return;
        }
        ++_value; 
    }
};

static inline 
DWORD    FastInfiniteWait(HANDLE hObj) throw()
{
    //_$ << '.';
#if 0
    return WaitForSingleObject(hObj, 0);
#else
    DWORD dwWaitResult;
    //static DWORD sleep_millis(NumProcessors()*2);
    while((dwWaitResult = WaitForSingleObject(hObj, 0)) == WAIT_TIMEOUT)
    {
        Sleep(8); //(sleep_millis);
    }
    return dwWaitResult;
#endif
}

class   timeout
{
private:
    unsigned int _since;
    unsigned int _due;
    //timeout();
    timeout(const timeout&);
protected:
    inline  bool timed_out() const
    {
        if (_due == INFINITE)
            return false; 
        unsigned int current = ::GetTickCount();
        // workaround possible overflow
        if (current >= _due )
            return (_due >= _since)? true : current < _since;
        return false;
    }
public:
    timeout(unsigned int millis_ = INFINITE, unsigned int since_ = 0)
        : _since((since_ == 0)? ((millis_ == INFINITE)? 0 : ::GetTickCount()) : since_)
        , _due((millis_ == INFINITE)? INFINITE : (_since + millis_))
    {
        if (_due == INFINITE && millis_ != INFINITE) // rare but possible case when _since + millis_ gives INFINITE
            ++_due;
    }

    inline operator bool() const
    {
        return timed_out();
    }

    inline void    sleep() const
    {
        ::Sleep(8);
    }
    inline unsigned int wait_time() const
    {
        if (_due == INFINITE)
            return 0;
        unsigned int current = ::GetTickCount();
        if (current <= _due)
            return _due - current;
        return _due + (INFINITE - current);
    }

    inline  bool wait(HANDLE handle_) const
    {
        for(;;)
        {
            DWORD wait_result = ::WaitForSingleObject(handle_, wait_time());
            ENSURE((WAIT_TIMEOUT == wait_result) || (WAIT_OBJECT_0 == wait_result));
            if (WAIT_OBJECT_0 == wait_result)
                return true;
            if (timed_out())
                break;
            sleep();
        }

        return false;
    }
};

#define DEFAULT_SPIN_MAX   4000


class CCriticalSection :
	public CRITICAL_SECTION
{
public:
#if (_WIN32_WINNT >= 0x0403)
	// Set the spin count for the critical section
	inline ULONG SetSpinCount( ULONG nSpinCount ) throw()
    {
	    return( ::SetCriticalSectionSpinCount( this, nSpinCount ) );
    }
#endif

	CCriticalSection()
    {
	    ::InitializeCriticalSection( this );
#if (_WIN32_WINNT >= 0x0403)
        SetSpinCount(DEFAULT_SPIN_MAX);
#endif
    }

#if (_WIN32_WINNT >= 0x0403)
	explicit CCriticalSection( ULONG nSpinCount )
    {
        ::InitializeCriticalSectionAndSpinCount( this, nSpinCount );
    }
#endif
	~CCriticalSection() throw()
    {
	    ::DeleteCriticalSection( this );
    }
	// Acquire the critical section
	inline void Enter()
    {
	    ::EnterCriticalSection( this );
    }

    // Release the critical section
	inline void Leave() throw()
    {
	    ::LeaveCriticalSection( this );
    }

#if (_WIN32_WINNT >= 0x0400)
	// Attempt to acquire the critical section
	inline BOOL TryEnter() throw()
    {
	    return( ::TryEnterCriticalSection( this ) );
    }
	BOOL Lock(DWORD dwTimeout = INFINITE) throw()
	{
        timeout to(dwTimeout);
        while(!TryEnter())
        {
            if (to)
                return FALSE;
            ::Sleep(1);
        }
        return TRUE;
	}
#else
	inline BOOL Lock() throw()
	{
		Enter();
		return TRUE;
	}
#endif

	inline void Unlock() throw()
	{
		Leave();
	}

};

class CCritSectEx 
{
private:
    // Declare most of the variables volatile, so that the compiler won't
    // try to optimize something important.
    volatile DWORD  m_dwOwner;
    volatile DWORD  m_dwLockCount;
    volatile DWORD  m_dwSpinMax;
    volatile LONG   m_nWaiters;

    volatile HANDLE m_hEvent;
    volatile BOOL   m_bEventSet;

    inline void AllocEvent()
    {
        if (!m_hEvent)
        {
            HANDLE hEvent = ::CreateEvent(NULL, FALSE, FALSE, NULL);
            ENSURE(NULL != hEvent);
            //RAISE_LASTERROR(NULL != hEvent);
            if (::InterlockedCompareExchangePointer(&m_hEvent, hEvent, NULL))
                VERIFY(::CloseHandle(hEvent)); // we're late
        }
    }

    DWORD SetSpinMax(DWORD dwSpinMax)
    {
        DWORD dwRet = m_dwSpinMax;
        if (NumProcessors() > 1)
            m_dwSpinMax = dwSpinMax;
        return dwRet;
    }

    inline BOOL PerfLockImmediate(DWORD owner_, DWORD times_ = 0)
    {
        m_bEventSet = FALSE; // Must set it BEFORE attempt to lock.

        if ( 0 == _InterlockedCompareExchange((volatile long*)&m_dwOwner, owner_, 0))
            return TRUE;
        while(times_--)
        {
            ::Sleep(1);
            if ( 0 == _InterlockedCompareExchange((volatile long*)&m_dwOwner, owner_, 0))
                return TRUE;
        }

        return FALSE;
    }

    BOOL PerfLockKernel(DWORD owner_, DWORD dwTimeout)
    {
        _ASSERT(m_hEvent);
        timeout to(dwTimeout);

        do
        {
            if (PerfLockImmediate(owner_))
                return TRUE;
        } while(to.wait(m_hEvent));
        return FALSE;
    }

    BOOL PerfLock(DWORD owner_, DWORD dwTimeout)
    {
        // Attempt spin-lock
        if (PerfLockImmediate(owner_, m_dwSpinMax))
            return TRUE;
        // Ensure we have the kernel event created
        AllocEvent();

        _ASSERT(m_dwOwner != owner_);
        _InterlockedIncrement(&m_nWaiters);
        BOOL bRet = PerfLockKernel(owner_, dwTimeout);
        _InterlockedDecrement(&m_nWaiters);

        return bRet;
    }


    CCritSectEx(const CCritSectEx&);
    CCritSectEx& operator=(const CCritSectEx&);

public:
    CCritSectEx()
    {
        // must be aligned on a 32-bit boundary
        _ASSERT(PROPERLY_ALIGNED(m_nLocker));
        ZeroMemory(this, sizeof(*this));
        SetSpinMax(DEFAULT_SPIN_MAX);
    }

    CCritSectEx(DWORD dwSpinMax)
    {
        // must be aligned on a 32-bit boundary
        _ASSERT(PROPERLY_ALIGNED(m_nLocker));
        ZeroMemory(this, sizeof(*this));
        SetSpinMax(dwSpinMax);
    }
    ~CCritSectEx()
    {
        _ASSERT(m_nLocker == 0);
        if (m_hEvent)
            ENSURE(::CloseHandle(m_hEvent));
    }

    BOOL    Lock(DWORD dwTimeout=INFINITE)
    {
        DWORD dwThreadId = GetCurrentThreadId();
        if (dwThreadId != m_dwOwner)
        {
            if (!PerfLockImmediate(dwThreadId) && !(dwTimeout && PerfLock(dwThreadId, dwTimeout)))
            {
                return FALSE;
            } 
            //m_dwOwner = dwThreadId;
        }

        ++m_dwLockCount;
        return TRUE;
    }

    void    Unlock()
    {
        _ASSERT(GetCurrentThreadId() == m_dwOwner);
        _ASSERT((int)m_dwLockCount > 0);
        if (--m_dwLockCount == 0)
        {
            m_dwOwner = 0;
            //m_nLocker = 0;

            if (m_nWaiters && !m_bEventSet)
            {
                m_bEventSet = TRUE;
                RAISE_LASTERROR(SetEvent(m_hEvent));
            }
        }
    }

    inline BOOL    TryLock()
    {
        return Lock(0);
    }

    // Acquire the critical section
    void Enter()
    {
        Lock();
    }
    // Release the critical section
    void Leave() throw()
    {
        Unlock();
    }
#if (_WIN32_WINNT >= 0x0403)
    // Set the spin count for the critical section
    ULONG SetSpinCount( ULONG nSpinCount ) throw()
    {
        return SetSpinMax(nSpinCount);
    }
#endif
#if (_WIN32_WINNT >= 0x0400)
    // Attempt to acquire the critical section
    BOOL TryEnter() throw()
    {
        return TryLock();
    }
#endif
    inline
    HANDLE  GetOwningThread() const
    {
        return (HANDLE)(DWORD_PTR)m_dwOwner; 
    }
    __declspec(property(get=GetOwningThread))
    HANDLE  OwningThread;
};

class CComFastCriticalSection //: public CCritSectEx
{
public:
    CComFastCriticalSection() throw()
        //: CCritSectEx()
    {
    }
    ~CComFastCriticalSection()
    {
    }
    HRESULT Lock() throw()
    {
        m_sec.Lock(); 
        return S_OK;
    }
    HRESULT Unlock() throw()
    {
        m_sec.Unlock();
        return S_OK;
    }
    HRESULT Init() throw()
    {
        return S_OK;
    }

    HRESULT Term() throw()
    {
        return S_OK;
    }   
    CCritSectEx  m_sec;
};

#if 0
class CComAutoFastCriticalSection : public CComFastCriticalSection
{
public:
    CComAutoFastCriticalSection()
    {
        HRESULT hr = CComFastCriticalSection::Init();
        if (FAILED(hr))
            AtlThrow(hr);
    }
    ~CComAutoFastCriticalSection() throw()
    {
        CComFastCriticalSection::Term();
    }
private :
    HRESULT Init(); // Not implemented. CComAutoCriticalSection::Init should never be called
    HRESULT Term(); // Not implemented. CComAutoCriticalSection::Term should never be called
};
#endif

class CComSafeDeleteFastCriticalSection : public CComFastCriticalSection
{
public:
    CComSafeDeleteFastCriticalSection(): m_bInitialized(false) 
    {
    }

    ~CComSafeDeleteFastCriticalSection() throw()
    {
        if (!m_bInitialized)
        {
            return;
        }
        m_bInitialized = false;
        CComFastCriticalSection::Term();
    }

    HRESULT Init() throw()
    {
        _ASSERT( !m_bInitialized );
        HRESULT hr = CComFastCriticalSection::Init();
        if (SUCCEEDED(hr))
        {
            m_bInitialized = true;
        }
        return hr;
    }

    HRESULT Term() throw()
    {
        if (!m_bInitialized)
        {
            return S_OK;
        }
        m_bInitialized = false;
        return CComFastCriticalSection::Term();
    }

    HRESULT Lock()
    {
        // CComSafeDeleteFastCriticalSection::Init or CComAutoDeleteFastCriticalSection::Init
        // not called or failed.
        // m_critsec member of CComObjectRootEx is now of type 
        // CComAutoDeleteFastCriticalSection. It has to be initialized
        // by calling CComObjectRootEx::_AtlInitialConstruct
        ASSUME(m_bInitialized);
        return CComFastCriticalSection::Lock();
    }

private:
    bool m_bInitialized;
};

class CComAutoDeleteFastCriticalSection : public CComSafeDeleteFastCriticalSection
{
private:
    // CComAutoDeleteCriticalSection::Term should never be called
    HRESULT Term() throw();
};
template <typename _CS = CCritSectEx>
class   _Lock
{
private:
    _Lock<_CS>();
    _Lock<_CS>(const _Lock<_CS>&);
    _Lock<_CS>& operator=(const _Lock<_CS>&);
protected:
    _CS&    _cs;
public:
    _Lock(_CS& cs_)
        : _cs(cs_)
    {
        _cs.Lock();
    }
    ~_Lock()
    {
        _cs.Unlock();
    }
};

#if 0
typedef CCriticalSection _MyCS;
#else
typedef CCritSectEx _MyCS;
#endif
typedef _Lock<_MyCS> Lock;

static  _MyCS g_lock;
static  DWORD   shared = 0;
const DWORD max_count = 10000000;
#define NUM_THREADS 8

#define BEGIN_LOCKED(x) { Lock __lck__(x);
#define END_LOCKED      }

DWORD  WINAPI thread_func(void* arg_)
{
    DWORD   tmp = 0;
    //_$ << "thread " << ::GetCurrentThreadId() <<" started" << $_;
    DWORD use = 0;
    do
    {
        //YieldProcessor();
        BEGIN_LOCKED(g_lock)
        tmp = shared;
        if (tmp < max_count)
            ++shared;
        else 
            break;
        ++use;
        END_LOCKED
    } while(true);
    _$ << "shared = " << shared << $_;
    _$ << "thread " << ::GetCurrentThreadId() << " used " << use << " times" << $_;
    return 0;
}

HANDLE  create_thread(LPTHREAD_START_ROUTINE proc_, LPDWORD thread_id_ = NULL, LPVOID param_ = NULL)
{
    return CreateThread(
          NULL,         //_In_opt_   LPSECURITY_ATTRIBUTES lpThreadAttributes,
          0,            //_In_       SIZE_T dwStackSize,
          proc_,        //_In_       LPTHREAD_START_ROUTINE lpStartAddress,
          param_,       //_In_opt_   LPVOID lpParameter,
          0,            //_In_       DWORD dwCreationFlags,
          thread_id_    //_Out_opt_  LPDWORD lpThreadId
    );
}

void test()
{
    HANDLE  threads[NUM_THREADS] = {NULL};

    //_$ << "test started" << $_;
    shared = 0;
    prec_timer t;
    t.start();
    for(size_t i = 0; i < NUM_THREADS; ++i)
    {
        threads[i] = create_thread(thread_func);
    }

    ::WaitForMultipleObjects(NUM_THREADS, threads, TRUE, INFINITE);
    _$ << max_count << " reached in " << t.stop() << " seconds" << $_;
    _$ << "test finished" << $_;
}
int _tmain(int argc, _TCHAR* argv[])
{
    prec_timer t;
    t.start();
    for(int i = 0; i < 20; ++i)
        test();
    _$ << "tests completed in " << t.stop() << " seconds" << $_;
    _$ << "program exits" << $_;
	return 0;
}

